package frist50;

import java.util.ArrayList;
import java.util.List;

public class T0039 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        return dp(candidates,candidates.length,target);
    }

    public List<List<Integer>> dp(int[] candidates,int n,int target){
        if (target==0)return new ArrayList<>(new ArrayList<>());
        if (n==0) return new ArrayList<>();
        List<List<Integer>> lists=new ArrayList<>();
        int can=candidates[n-1];
        for (int i = 0; i<n ; i++) {
            int targetTmp=target-can*i;
            if (targetTmp<0)break;
            List<Integer> list=new ArrayList<>();
            List<List<Integer>> t=dp(candidates,n-1,targetTmp);
            for (int j = 0; j <i ; j++) {
                for(List<Integer> l:t){
                    l.add(can);
                }
            }
            lists.addAll(t);
        }
        return lists;

    }
}
